package example.双指针.快慢指针.链表环;

public class Demo1 {

    /**
     * 我们使用两个指针，fast 与 slow。
     * 1、它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，
     * 而fast 指针向后移动两个位置。如果链表中存在环，
     * 则 fast 指针最终将再次与 slow 指针在环中相遇。
     * 2、当发现 slow 与 fast 相遇时，我们再额外使用一个指针 cur。起始，它指向链表头部；
     * 随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇,环点就是入口
     *
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead, slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;

            slow = slow.next;
            if (fast == slow) {
                ListNode current = pHead;
                while (current != slow) {
                    slow = slow.next;
                    current = current.next;
                }
                return current;
            }
        }
        return null;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
